//
// Created by lanlu on 2025/8/13.
//

#include <vector>
#include <queue>
#include <iostream>
using namespace std;

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        // 接受城市数量
        int n = isConnected.size();
        // 记录城市是否被访问
        vector<bool> visited(n, false);
        // 省份数量
        int count = 0;
        for (int i = 0; i < n; i++)
        {
            // 如果城市没有被访问 代表找到一个新省份
            if (!visited[i])
            {
                count++;
                bfs(isConnected, visited, i);
            }
        }
        return count;
    }

    // 广度优先搜索
    void bfs(vector<vector<int>> &isConnected, vector<bool> &visited, int i)
    {
        // 使用队列来记录访问到哪个城市
        queue<int> q;
        q.push(i);
        visited[i] = true;

        // 循环处理所有城市
        while (!q.empty())
        {
            // 取出队首的城市
            int cur = q.front();
            q.pop();

            // 检查当前城市和其他城市的连接情况
            for (int j = 0; j < isConnected.size(); j++)
            {
                // 如果当前城市 和 j对应的城市相连  并且 j没有被访问过
                if (isConnected[cur][j] == 1 && !visited[j])
                {
                    visited[j] = true;
                    q.push(j);
                }
            }
        }
    }
};

int main() {
    vector<vector<int>> isConnected = {{1,1,0},{1,1,0},{0,0,1}};
    int circle_num = Solution().findCircleNum(isConnected);
    cout << circle_num << endl;
}
